<!DOCTYPE html>
<html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-0 vector-toc-not-available vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-0 skin-theme-clientpref-day vector-sticky-header-enabled" lang="de" dir="ltr"><head>
<meta charset="UTF-8">
<title>Linearer Graph</title>
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<link rel="icon" type="image/png" href="./_res_/favicon.png">
<link rel="canonical" href="https://de.wikipedia.org/wiki/Linearer_Graph"> <link href="./_mw_/ext.cite.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.math.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.wikimediamessages.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.icons.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.search.codex.styles.css" rel="stylesheet" type="text/css">
<link href="./_mw_/skins.vector.styles.css" rel="stylesheet" type="text/css">
<meta name="ResourceLoaderDynamicStyles" content="">
<link href="./_mw_/ext.gadget.citeRef.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.defaultPlainlinks.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonHide.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonLayout.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiCommonStyle.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiDarkmode.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.dewikiResponsive.css" rel="stylesheet" type="text/css">
<link href="./_mw_/ext.gadget.specialSearch.css" rel="stylesheet" type="text/css">
<link rel="stylesheet" type="text/css" href="./_mw_/site.styles.css">
<link rel="stylesheet" type="text/css" href="./_mw_/noscript.css">
<link rel="stylesheet" type="text/css" href="./_res_/footer.css">
<link rel="stylesheet" type="text/css" href="./_res_/vector-2022.css">
</head>
<body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject page-Linearer_Graph rootpage-Linearer_Graph skin-vector-2022 action-view">
<div class="mw-page-container">
<div class="mw-page-container-inner">
<div class="mw-content-container">
<main id="content" class="mw-body">
<header class="mw-body-header vector-page-titlebar">
<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Linearer Graph</span></h1>
</header>
<a id="top"></a>
<div id="bodyContent" class="vector-body ve-init-mw-desktopArticleTarget-targetContainer" aria-labelledby="firstHeading" data-mw-ve-target-container="">
<div id="contentSub">
<div id="mw-content-subtitle"></div>
</div>
<div id="mw-content-text" class="mw-body-content mw-content-ltr" lang="de" dir="ltr"><div class="mw-content-ltr mw-parser-output" lang="de" dir="ltr">
<p>Ein <b>linearer Graph</b> oder <b>Pfadgraph</b> ist ein <a href="Graph_(Graphentheorie)" title="Graph (Graphentheorie)">Graph</a>, der nur aus einem <a href="Pfad_(Graphentheorie)" class="mw-redirect" title="Pfad (Graphentheorie)">Pfad</a> besteht. Lineare Graphen sind einfache Beispiele für <a href="Baum_(Graphentheorie)" title="Baum (Graphentheorie)">Bäume</a>. Sie haben keine Verzweigungen, sodass die mittleren <a href="Knoten_(Graphentheorie)" title="Knoten (Graphentheorie)">Knoten</a> den Grad 2, und die Endknoten den Grad 1 haben. Der lineare Graph mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mi>n</mi>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle n}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span> Knoten wird mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P_{n}}">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<msub>
<mi>P</mi>
<mrow class="MJX-TeXAtom-ORD">
<mi>n</mi>
</mrow>
</msub>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle P_{n}}</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5949c8b1de44005a1af3a11188361f2a830842d1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.711ex; height:2.509ex;" alt="{\displaystyle P_{n}}" loading="lazy"></span> bezeichnet.
</p>
<div class="mw-heading mw-heading2"><h2 id="Graziöse_Beschriftung"><span id="Grazi.C3.B6se_Beschriftung"></span>Graziöse Beschriftung</h2></div>
<p>Lineare Graphen sind <a href="Grazi%C3%B6se_Beschriftung" title="Graziöse Beschriftung">graziöse Graphen</a>.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Eine graziöse Beschriftung entsteht, wenn die Knoten mit den Zahlen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 1,n,2,n-1,3,n-3,\ldots }">
<semantics>
<mrow class="MJX-TeXAtom-ORD">
<mstyle displaystyle="true" scriptlevel="0">
<mn>1</mn>
<mo>,</mo>
<mi>n</mi>
<mo>,</mo>
<mn>2</mn>
<mo>,</mo>
<mi>n</mi>
<mo>−<!-- − --></mo>
<mn>1</mn>
<mo>,</mo>
<mn>3</mn>
<mo>,</mo>
<mi>n</mi>
<mo>−<!-- − --></mo>
<mn>3</mn>
<mo>,</mo>
<mo>…<!-- … --></mo>
</mstyle>
</mrow>
<annotation encoding="application/x-tex">{\displaystyle 1,n,2,n-1,3,n-3,\ldots }</annotation>
</semantics>
</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/f4d669689ff4eb16abef5ac9628167a5832c7a42.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:24.604ex; height:2.509ex;" alt="{\displaystyle 1,n,2,n-1,3,n-3,\ldots }" loading="lazy"></span> beschriftet werden. Diese Beschriftung ist bipartit.
</p>
<dl><dd><span class="mw-default-size" typeof="mw:File"></span></dd></dl>
<p>Eine entsprechende graziöse Beschriftung für den linearen Graphen mit fünf Knoten zeigt die folgende Zeichnung.
</p>
<dl><dd><span class="mw-default-size" typeof="mw:File"></span></dd></dl>
<div class="mw-heading mw-heading2"><h2 id="Siehe_auch">Siehe auch</h2></div>
<ul><li><a href="Kreisgraph" title="Kreisgraph">Kreisgraph</a></li>
<li><a href="Sterngraph" title="Sterngraph">Sterngraph</a></li>
<li><a href="Leitergraph" title="Leitergraph">Leitergraph</a></li></ul>
<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>
<ol class="references">
<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text">Michelle Edwards, Lea Howard: <cite style="font-style:italic">A survey of graceful trees</cite>. In: <cite style="font-style:italic">Atlantic Electronic Journal of Mathematics</cite>. 1. Jahrgang, <span style="white-space:nowrap">Nr.<span style="display:inline-block;width:.2em"> </span>1</span>, 2006, <span style="white-space:nowrap">S.<span style="display:inline-block;width:.2em"> </span>5–29</span> (<a rel="nofollow" class="external text" href="http://euclid.trentu.ca/aejm/V1N1/Edwards.v1n1.pdf">trentu.ca</a> [PDF]).<span class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Ajournal&rfr_id=info:sid/de.wikipedia.org:Linearer+Graph&rft.atitle=A+survey+of+graceful+trees&rft.au=Michelle+Edwards%2C+Lea+Howard&rft.date=2006&rft.genre=journal&rft.issue=1&rft.jtitle=Atlantic+Electronic+Journal+of+Mathematics&rft.pages=5-29&rft.volume=1.+Jahrgang" style="display:none"> </span> </span>
</li>
</ol></div><!--htdig_noindex--><div><div class="zim-footer">
Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2015-07-17" href="https://de.wikipedia.org/wiki/?title=Linearer_Graph&oldid=144098776">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.
</div>
</div><!--/htdig_noindex--></div>
</div>
</main>
</div>
</div>
</div>
<script src="./_webp_/webpHandler.js"></script>
</body></html>